package subject_set.offer100;

import java.util.PriorityQueue;

/**
 * @author haomin
 * @date 2022/10/20 16:13
 **/
public class Offer41 {
    class MedianFinder {
        PriorityQueue<Integer> l;
        PriorityQueue<Integer> r;
        /** initialize your data structure here. */
        public MedianFinder() {
            l = new PriorityQueue<>((o1, o2) -> (o2-o1));
            r = new PriorityQueue<>();
        }

        public void addNum(int num) {
            l.offer(num);
            r.offer(l.poll());
            if(l.size() + 1 < r.size()){
                l.offer(r.poll());
            }
        }

        public double findMedian() {
            if(l.size() != r.size()) return r.peek();
            else return (double)(l.peek() + r.peek()) / 2;
        }
    }
}